package chapter02;

import java.util.Arrays;

public class ClimbStairs70 {
    /**
     * 记忆化搜索 process(pos,n)
     * 递归出口
     * 1).pos==n
     *  return 1
     * 2).pos==n+1
     *  return 0
     * 3).return process(pos+1,n)+process(pos+2,n)
     * 为了减少重复尝试 添加一个缓存数组dp
     * 将递归改为动态规划
     */
    //记忆化搜索
    public int climbStairs(int n) {
        int[] dp=new int[n+1];
        Arrays.fill(dp,-1);
        return process(0,n,dp);
    }

    public int process(int pos,int n,int[] dp){
        if(dp[pos]!=-1){
            return dp[pos];
        }
        if(pos==n){
            dp[pos]=1;
            return dp[pos];
        }
        if(pos==n+1){
            dp[pos]=0;
            return dp[pos];
        }
        dp[pos]=process(pos+1,n,dp)+process(pos+2,n,dp);
        return dp[pos];
    }

    //动态规划
    public int climbStairs1(int n) {
        int[] dp=new int[n+2];
        dp[n]=1;
        for(int i=n-1;i>=0;i--){
            dp[i]=dp[i+1]+dp[i+2];
        }
        return dp[0];
    }
}
